{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style=\"text-align: center;font-size: 33px;font-weight:bold;\"> <span style=\"color:DarkGoldenrod\">&lt;&lt; 算法 &gt;&gt;</span></p>\n",
    "<p style=\"text-align: center;font-size: 25px;font-weight:bold;\"> <span style=\"color:Goldenrod\">&lt;&lt; Algorithm &gt;&gt;</span></p>\n",
    "<p style=\"text-align: right; font-size:15px; font-weight:normal\">----`*程序设计*`的_**灵魂**_</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. 算法的由来\n",
    "#### 1.1 科学发展的需要\n",
    "例如：如何计算圆周率$\\pi$与自然对数的底$\\mathit{e}$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": []
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#include <iomanip>\n",
    "#include <iostream>\n",
    "#include <math.h>\n",
    "using namespace std;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(double) 3.141593\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M_PI"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(double) 2.718282\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M_E"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.2 工程技术的需要\n",
    "例如：二进制数的提出（为计算机电子电路设计的理论依据）\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": []
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "void bin(unsigned int n,unsigned int nc)\n",
    "{\n",
    "    if(n>1)\n",
    "      bin(n/2,nc);\n",
    "    cout<<n%2;\n",
    "    if(n==nc) cout<<endl;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000\n",
      "1001\n",
      "11111000011\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(void) @0x7f74e79a2b68\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bin(8,8);\n",
    "bin(9,9);\n",
    "bin(1987,1987);    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从专业的角度上说。要掌握好C语言，特别需要了解**二进制数**在计算机中的**存储`、`排列**方式！"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "又例如：行车导航中，确定到达目的地的最短路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.3 经济运作的需要\n",
    "例如：确定公司的产品组合，在有限的资源下获取最大的经济利益 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "极大化：$\\sum_i^n a_i x_i$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "满足： $\\sum_i^n c_i x_i \\le b_i$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. 算法的分类\n",
    "#### 2.1 数值计算类算法\n",
    "比计算机本身要古老得多，人类文明发展过程中遇到的各种数值计算问题，其通用解法均课归于此类<br>\n",
    "例如： 自然对数$\\mathit{e}$与圆周率$\\pi$的计算方法\n",
    "#### 2.2 信息处理类算法（互联网时代的主要算法构成）\n",
    "* 对结构化信息（数据）进行处理（例如：学生信息的增、删、改、查）\n",
    "* 对非结构化信息（数据）进行处理（例如：搜索引擎（Google,Baidu））\n",
    "* 对信息进行加密、解密 （目的：提高信息的安全性）\n",
    "* 对视频、图像数据进行压缩、解压缩（目的：降低网络传输、数据存储的负担）\n",
    "* 网络数据的拆分、传递、组合（目的：形成互联网）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.3 人工智能类算法（`AI`:Artifical Intellience）（人类社会已经半只脚踏入了人工智能时代！）\n",
    "最终目标： 我们希望计算机、机器人能够像人类一样听、说、读、写、看、玩、思考<br>\n",
    "已经落地的产品： \n",
    "* 各类语音助手（微软、苹果、谷歌）\n",
    "* 电子商务中的个性化推荐（亚马逊、京东、阿里巴巴）\n",
    "* 运货机器人（京东，阿里巴巴，亚马逊）\n",
    "* 自动驾驶（特斯拉，谷歌，百度）\n",
    "* 对弈软件（浪潮天梭，Google DeepMind：Alpha GO！）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. 算法的作用\n",
    "#### 3.1 程序=数据+算法\n",
    "#### 3.2 满足文化、科技、经济发展需求"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. 算法的形成与表达\n",
    "1. 确定问题并找到问题的**解决方法**\n",
    "2. 确定算法的各个步骤，以`自然语言`进行表达\n",
    "3. 绘制**算法流程图**（掌握:传统流程图;了解：BS流程图）\n",
    "4. 书写**伪代码**（符号$\\rightarrow$的含义？）\n",
    "5. 正式使用计算机语言进行**编程**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.1 算法流程图\n",
    "* 传统流程图 <br>\n",
    "传统流程图中矩形代表处理过程，菱形代表判断过程，以直线或折线确定各处理、判断过程的先后次序或形成循环。<br>\n",
    "传统流程图的基本组件<br>\n",
    "![基本元素1](./Resources/flow-ele.png)\n",
    "基本组件组合成图<br>\n",
    "![传统流程图](./Resources/flow-demo.svg)\n",
    "* NS流程图<br>\n",
    "结构化流程图中，循环使用大框表达，判断使用三分框表达。增强了算法流程图的可读性。<br>\n",
    "NS流程图的基本元素<br>\n",
    "![基本元素2](./Resources/ns-ele.png)\n",
    "基本元素组合成图<br>\n",
    "![结构化流程图](./Resources/ns-demo.png)\n",
    "* PAD流程图<br>\n",
    "PAD流程图采用树型结构表达循环与判断，可用于表达`极其复杂`的程序设计<br>\n",
    "PAD流程图的基本元素<br>\n",
    "![基本元素3](./Resources/pad-ele.png)\n",
    "基本元素组合成图<br>\n",
    "![PAD流程图](./Resources/pad-demo.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 伪代码\n",
    "**示例:课程质量统计**<br>\n",
    "<div style=\" overflow: hidden;\n",
    "  background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "  position: relative;\n",
    "  left: 50%;\n",
    "  background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "  position: relative;\n",
    "  left: -50%;\n",
    "  background-color: white;\">\n",
    "<p style=\"text-align: left; font-size:15px; font-weight:normal\">\n",
    "初始化`合格人数`:   $0 \\rightarrow p$<br>\n",
    "初始化`不合格人数`: $0 \\rightarrow f$<br>\n",
    "初始化`学生序号`:   $0 \\rightarrow s$<br>\n",
    "while 学生序号 $s<100$<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;    读取第$s$个学生的成绩<br> \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;    if 成绩合格<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;        $p+1 \\rightarrow p$<br> \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;    else<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;        $f+1 \\rightarrow f$<br> \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;    $s+1 \\rightarrow s$<br>\n",
    "print $p$<br>\n",
    "print $f$<br>\n",
    "if $p>80$<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;    print 课程达标<br>\n",
    "</p>\n",
    "</div>\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 例一\n",
    "**求：** **$\\frac{1}{1\\times 2\\times 3 \\times 4\\times 5 \\cdots \\times 1000}$**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**方法一，采用迭代的方式：**<br>\n",
    "<div style=\" overflow: hidden;\n",
    "  background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "  position: relative;\n",
    "  left: 50%;\n",
    "  background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "  position: relative;\n",
    "  left: -50%;\n",
    "  background-color: white;\">\n",
    "<p style=\"text-align: left; font-size:15px; font-weight:normal\">\n",
    "计算$\\frac{1}{1\\times 2}$<br>\n",
    "将上一步的结果乘以$\\frac{1}{3}$<br>\n",
    "将上一步的结果乘以$\\frac{1}{4}$<br>\n",
    "将上一步的结果乘以$\\frac{1}{5}$<br>\n",
    "将上一步的结果乘以$\\frac{1}{6}$<br>\n",
    "一直写下去......<br>\n",
    "将上一步的结果乘以$\\frac{1}{1000}$<br>\n",
    "</p></div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**方法二, 使用循环并在循环中改变被乘数**\n",
    "<div style=\" overflow: hidden;\n",
    "  background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "  position: relative;\n",
    "  left: 50%;\n",
    "  background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "  position: relative;\n",
    "  left: -50%;\n",
    "  background-color: white;\">\n",
    "<p style=\"text-align: left; font-size:15px; font-weight:normal\">\n",
    "初始化结果:    $1 \\rightarrow r$<br>\n",
    "初始化被乘数的倒数:    $ 1 \\rightarrow k$<br>\n",
    "当  $k \\le 1000$ 如是：<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;计算$\\frac{r}{k}$<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;令$r$为计算结果<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;令$k$加1<br>\n",
    "否则&nbsp;&nbsp;输出$r$<br>\n",
    "</p></div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**将自然语言转化为流程图**<br>\n",
    "**方法二的流程图**<br>\n",
    "![方法二](./Resources/flow-1s.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**将流程图转化为伪代码**<br>\n",
    "**示例:阶乘的倒数`伪码`**<br>\n",
    "<div style=\" overflow: hidden;\n",
    "  background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "  position: relative;\n",
    "  left: 50%;\n",
    "  background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "  position: relative;\n",
    "  left: -50%;\n",
    "  background-color: white;\">\n",
    "<p style=\"text-align: left; font-size:15px; font-weight:normal\">\n",
    "初始化`计算结果`:   $1 \\rightarrow r$<br>\n",
    "初始化`计数变量`:   $1 \\rightarrow k$<br>\n",
    "while $k \\le 1000$<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;    $\\frac{r}{k} \\rightarrow r$<br> \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;    $k+1 \\rightarrow k$<br>\n",
    "print $r$<br>\n",
    "</p>\n",
    "</div>\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**将伪代码转化为C语言**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.07151e-158\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(std::basic_ostream<char, std::char_traits<char> >::__ostream_type &) @0x7f74fe621e40\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "double r=1;\n",
    "int   k=1;\n",
    "while(k<=100){\n",
    "r=r/k;\n",
    "k=k+1;\n",
    "}\n",
    "//printf(\"%e\",r)\n",
    "cout<<setprecision(6)<<r<<endl"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 例二\n",
    "**求：** **$1-\\frac{1}{3}+\\frac{1}{5}-\\frac{1}{7}+\\cdots$**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**方法, 在循环中改变加数与符号**\n",
    "<div style=\" overflow: hidden;\n",
    "  background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "  position: relative;\n",
    "  left: 50%;\n",
    "  background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "  position: relative;\n",
    "  left: -50%;\n",
    "  background-color: white;\">\n",
    "<p style=\"text-align: left; font-size:15px; font-weight:normal\">\n",
    "初始化结果:    $0 \\rightarrow r$<br>\n",
    "初始化计数变量:    $ 1 \\rightarrow k$<br>\n",
    "当  $k \\le 1000$ 如是：<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;计算$ \\frac{(-1)^{k+1}}{2k-1}$<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;以上一步的结果增加$r$的值<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;令$k$加1<br>\n",
    "否则&nbsp;&nbsp;输出$r$<br>\n",
    "</p></div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**将自然语言转化为流程图**<br>\n",
    "**例二的流程图**<br>\n",
    "![方法二](./Resources/flow-2.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**将流程图转化为伪代码**<br>\n",
    "**示例:例二`伪码`**<br>\n",
    "<div style=\" overflow: hidden;\n",
    "  background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "  position: relative;\n",
    "  left: 50%;\n",
    "  background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "  position: relative;\n",
    "  left: -50%;\n",
    "  background-color: white;\">\n",
    "<p style=\"text-align: left; font-size:15px; font-weight:normal\">\n",
    "初始化`计算结果`:   $0 \\rightarrow r$<br>\n",
    "初始化`计数变量`:   $1 \\rightarrow k$<br>\n",
    "初始化`符号变量`:   $1 \\rightarrow s$<br>\n",
    "while $k \\le 1000$<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;    $-1 \\times s \\rightarrow s$<br> \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;    $r+\\frac{s}{2k-1} \\rightarrow r$<br> \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;    $k+1 \\rightarrow k$<br>\n",
    "print $r$<br>\n",
    "</p>\n",
    "</div>\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.14159275358980139004\n",
      "3.14159270358981945748\n",
      "3.14159268692330062578\n",
      "3.14159267859046487104\n",
      "3.14159267359025085042\n",
      "3.14159267025681776531\n",
      "3.14159266787567093004\n",
      "3.14159266608963338996\n",
      "3.14159266470069509225\n",
      "3.14159266358932587337\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(void) @0x7f74e79a2b68\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "void demo_2(){\n",
    "long k=1;\n",
    "double r=0.0;\n",
    "double s=-4.0;\n",
    "while(k<=100000000){\n",
    "s*=-1;\n",
    "r+=s/(2*k-1);\n",
    "k++;\n",
    "if(k%10000000==0) cout<<setprecision(21)<<r<<endl;\n",
    "}\n",
    "}\n",
    "demo_2();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "7\n",
      "9\n",
      "11\n",
      "13\n",
      "17\n",
      "19\n",
      "23\n",
      "25\n",
      "29\n",
      "31\n",
      "37\n",
      "41\n",
      "43\n",
      "47\n",
      "49\n",
      "53\n",
      "59\n",
      "61\n",
      "67\n",
      "71\n",
      "73\n",
      "79\n",
      "83\n",
      "89\n",
      "97\n"
     ]
    },
    {
     "data": {
      "text/plain": []
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int isPrime(unsigned int k){\n",
    "for(int t=2;t<sqrt(k);t++){\n",
    "if(k%t==0) return 0;\n",
    "} \n",
    "return -1;\n",
    "}\n",
    "for(int k=1;k<100;k++) \n",
    "if(isPrime(k)) cout<<k<<endl;"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++11",
   "language": "C++",
   "name": "cling-cpp11"
  },
  "language_info": {
   "codemirror_mode": "c++",
   "file_extension": ".c++",
   "mimetype": "text/x-c++src",
   "name": "c++"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
